import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description: 数组包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。在O(n)时间内完成
 * User: 15085202591
 * Date: 2022-11-25
 * Time: 22:21
 */

public class MissNums{
    public static int findNum(int[] array){
        //求和相减 求和相减
        //（n+1）*n/2 - (数组累加和)
        //时间复杂度：O(N)
        //空间复杂度：O(1)

        int k = array.length+1;
        int sum = k*(k+1)/2;
        int sum2 = 0;
        for (int i = 0; i < array.length; i++) {
            sum2+=array[i];
        }
        return sum - sum2;
    }
    public static int find2Num(int[] array){
        //开辟额外数组，找单身狗
        //时间复杂度：O(N)
        //空间复杂度：O(1)
        int[] array2 = new int[array.length + array.length+1];
        for (int i = 0; i < array2.length; i++) {
            if(i < array.length){
                array2[i] = array[i];
            }else {
                array2[i] = i -array.length;
            }
        }
        int n = 0;
        for (int i = 0; i < array2.length; i++) {
            n = n ^ array2[i];
        }
        return n;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] array = new int[]{1,2,3,4,5,7,8};
        System.out.println(findNum(array));
        System.out.println(find2Num(array));
    }
}
